import java.util.*;

public class TestHeap {
    public int[] elem;
    public int usedSize;
    public TestHeap() {
        this.elem = new int[10];
        this.usedSize = 0;
    }
    public void initArray(int[] array){
        elem = Arrays.copyOf(array,array.length);
        usedSize = elem.length;
    }
    public void createHeap(){
        for (int parent = (usedSize-1-1)/2; parent >=0 ; parent--) {
            shiftDown(parent,usedSize);
        }
    }
    private void shiftDown(int parent,int len){
        int child=2*parent+1;
        while (child<len){
            if (child+1<len&&elem[child]<elem[child+1]){
                child++;
            }
            if (elem[child]>elem[parent]){
                swap(elem,child,parent);
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }
    public  void heapSodr(){
        int end =usedSize-1;
        while (end>0){
            swap(elem,0,end);
            shiftDown(0,end);
            end--;

        }
    }

    public void insert(int n){
        if (isFull()){
            elem=Arrays.copyOf(elem,elem.length*2);
        }
        this.elem[usedSize]=n;
        usedSize++;
        shiftUp(usedSize-1);
    }
    public void shiftUp(int child){
        int parent=(child-1)/2;
        while (child>0){
            if (elem[child]>elem[parent]){
                swap(elem,child,parent);
                child=parent;
                parent=(child-1)/2;
            }else {
                break;
            }
        }
    }
    public boolean isFull(){
        return usedSize==elem.length;
    }
    public int delete(){
        if (isempty()){
            return -1;
        }
        int old = elem[0];
        swap(elem,0,usedSize-1);
        usedSize--;
        shiftDown(0,usedSize);
        return old;
    }
    public boolean isempty(){
        return usedSize==0;
    }
    private void swap(int[] array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }

    public static void main(String[] args) {
        TestHeap testHeap=new TestHeap();
        int[] array={27,15,19,18,28,34,65,49,25,37};
        testHeap.initArray(array);
        testHeap.createHeap();
        testHeap.heapSodr();
        System.out.println("kkkskskss");
    }

    public static void topK(int[] array,int k){
        PriorityQueue<Integer> maxQ=new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        for (int i = 0; i < array.length; i++) {
            maxQ.offer(array[i]);
        }
        for (int i = 0; i <= k; i++) {

                int val = maxQ.poll();
                System.out.println(val);

        }
    }
    public static int[] topK2(int[] array,int k){
        PriorityQueue<Integer> maxQ=new PriorityQueue<>( k,new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        for (int i = 0; i < array.length; i++) {
            if (maxQ.size()<k){
                maxQ.offer(array[i]);
            }else {
                int val=maxQ.peek();
                if (array[i]<val){
                    maxQ.poll();
                    maxQ.offer(array[i]);
                }
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {

            ret[i] = maxQ.poll();

        }
        return ret;
    }
    public static void main2(String[] args) {
        int[] array={27,88,99,77,55,11,22,66,44,33};
        int[] val=topK2(array,5);
        for (int i = 0; i < val.length; i++) {
            System.out.println(val[i]);
        }
    }
    public int firstUniqChar(String s){
       int[] array=new int[26];
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);

        }
    }
}
